\chapter{图形学介绍}

计算机图形学（\textit{computer graphics}）这个术语描述了任何使用计算机来创建和操作图像的场景。本书介绍了可用于创建各种图像的算法和数学工具——逼真的视觉效果、丰富的技术插图或精美的计算机动画。图形可以是二维的，也可以是三维的；图像可以是合成的，也可以是通过处理照片产生的。本书是关于基本算法和数学的书，特别是那些用于制作三维物体和场景的合成图像的算法。

实际上，研究计算机图形学不可避免地需要了解特定的硬件和文件格式，通常还需要了解一两个图形API（参见1.3节），而计算机图形学又是一个快速发展的领域，这些知识的具体内容也在不断更新变化。因此在本书中，我们尽量避免依赖任何特定的硬件或API，同时鼓励读者结合自己软/硬件环境的相关文档来学习本书。幸运的是，计算机图形学领域的术语和概念足够标准，本书的讨论应能很好地反映到大多数环境。

\marginpar{
  \begin{center}
    \begin{note}\\
      \textcolor{lightgreen}{API}:应用程序编程接口。
    \end{note}
  \end{center}
}

本章定义了一些基本术语，并提供了一些历史背景，以及与计算机图形学相关的信息源。

\section{图形学领域}

对任何领域强加分类都是危险的，但大多数图形学从业者都对计算机图形学的以下主要领域达成一致:
\begin{itemize}
  \item \textcolor{lightgreen}{建模（\textit{modeling}）}涉及到通过数学将形状和外观属性描述为可存储在计算机中的形式。例如，可以将咖啡杯描述为一组有序的三维点、一些连接这些点的插值规则和一个描述光线如何与杯子相互作用的反射模型。
  \item \textcolor{lightgreen}{渲染（\textit{rendering}）}是一个从艺术中继承下来的术语，涉及到从三维计算机模型创建着色图像。
  \item \textcolor{lightgreen}{动画（\textit{animation}）}是一种通过图像序列创造运动错觉的技术。动画使用建模和渲染，但增加了随时间移动的关键问题，这通常在基本建模和渲染中不会涉及到。
\end{itemize}
还有许多其他涉及计算机图形学的领域，至于它们是否属于图形学的核心领域，仁者见仁，智者见智。这些内容至少都会在本书中提及。此类相关领域包括以下内容：
\begin{itemize}
  \item \textcolor{lightgreen}{用户交互（\textit{user interaction}）}涉及输入设备（例如鼠标和手写板）、应用程序、对用户的图像反馈以及其他感官反馈之间的接口。从历史上看，该领域与图形有关，主要是因为计算机图形学的研究人员最早接触到了现在无处不在的输入和输出设备。
  \item \textcolor{lightgreen}{虚拟现实（\textit{virtual reality}）}试图让用户沉浸在一个三维虚拟世界中。这通常要求至少有立体图形和对头部运动的反应。对于真正的虚拟现实，还应该提供声音和力量的反馈。因为这一领域需要先进的三维图形和先进的显示技术，所以它通常与图形学密切相关。
  \item \textcolor{lightgreen}{可视化（\textit{visualization}）}试图通过视觉显示让用户深入了解复杂的信息。通常，在一个可视化问题中有一些图形学问题需要解决。
  \item \textcolor{lightgreen}{图像处理（\textit{image processing}）}涉及对二维图像的操作，在图形学和视觉领域均有应用。
  \item \textcolor{lightgreen}{三维扫描（\textit{three-dimensional scanning}）}使用测距技术来创建测定的三维模型。这类模型对于创造丰富的视觉图像很有帮助，而处理这种模型往往需要图形算法。
  \item \textcolor{lightgreen}{计算摄影（\textit{computational photography}）}使用计算机图形学、计算机视觉和图像处理方法来实现拍摄物体、场景和环境的新方法。
\end{itemize}

\section{主要应用}

几乎任何工作都可以在一定程度上涉及到计算机图形学，但计算机图形学技术的主要消费者包括以下行业：
\begin{itemize}
  \item \textcolor{lightgreen}{视频游戏（\textit{video games}）}越来越多地使用复杂的三维模型和渲染算法。
  \item \textcolor{lightgreen}{卡通片（\textit{cartoons}）}通常由三维模型直接渲染得到。许多传统的二维卡通片会使用由三维模型渲染的背景，这使得连续移动的视角不必占用艺术家大量的时间。
  \item \textcolor{lightgreen}{视觉效果（\textit{visual effects}）}几乎使用了所有类型的计算机图形学技术。几乎每部现代电影都使用数字合成技术来叠加背景与单独拍摄的前景。许多电影还使用三维建模和动画来创造合成环境、物体甚至人物，而大多数观众都不会怀疑这是假的。
  \item \textcolor{lightgreen}{动画电影（\textit{animated films}）}使用了许多视觉效果会用到的技术，但不一定要追求图像的真实性。
  \item \textcolor{lightgreen}{\textit{CAD/CAM}}是指计算机辅助设计（\textit{computer-aided design}）和计算机辅助制造（\textit{computer-aided manufacturing}）。这些领域利用计算机技术在计算机上设计零件和产品，然后利用这些虚拟设计来指导制造过程。例如，许多机械零件是在三维计算机建模软件包中设计的，然后在计算机控制的铣削设备上自动生产。
  \item \textcolor{lightgreen}{仿真（\textit{simulation}）}可以被视为精确的视频游戏。例如，飞行模拟器使用复杂的三维图形来模拟驾驶飞机的体验。这样的模拟对于安全关键领域的初始培训（例如驾驶汽车）以及对于有经验的用户的场景培训（比如在实际操作中成本太高或太危险的特定灭火情况）都是非常有用的。
  \item \textcolor{lightgreen}{医学影像（\textit{medical imaging}）}根据扫描的病人数据创建有意义的图像。例如，计算机断层扫描（\textit{CT, computed tomography}）数据集是由包含密度值的大型三维矩阵组成的。计算机图形学被用来创建阴影图像，帮助医生从这些数据中提取最突出的信息。
  \item \textcolor{lightgreen}{信息可视化（\textit{information visualization}）}为不一定具有“自然的”视觉描述的数据创建图像。例如，十只不同股票价格的时间趋势没有明显的视觉描述，但巧妙的图形技术可以帮助人类看到这些数据的模式。
\end{itemize}

\section{图形API}

使用图形库的一个关键部分在于和图形API（\textit{graphics API}）打交道。应用程序接口（\textit{API, application program interface}）是执行一系列相关操作的标准函数集合，而图形API是执行诸如将图像和三维表面绘制到屏幕上的窗口等基本操作的函数集合。

每个图形程序都需要使用两个相关的API：一个图形API用于视觉输出，一个用户界面API用于从用户那里获得输入。目前有两种主流的图形API和用户界面API模式：第一种是集成的方式，以Java为例，其中图形和用户界面工具包是集成的、可移植的包，作为语言的一部分得到完全的标准化和支持。第二种是以Direct3D和OpenGL为代表的模式，其中绘图命令是与C++等语言相联系的软件库的一部分，而用户界面软件是一个独立的实体，可能因系统而异。在后一种方法中，编写可移植的代码会有点困难，尽管对于简单的程序，可能会使用可移植的库层来封装系统特定的用户界面代码。

无论你选择什么样的API，基本的图形调用将大致相同，而且本书的概念也适用。

\section{图形管道}

今天，每台台式电脑都有一个强大的三维图形管道（\textit{graphics pipeline}）。这是一个特殊的软/硬件子系统，可以有效地绘制透视的三维图元。这些系统一般都对包含共享顶点的三维三角形的处理过程进行了优化。管道中的基本操作是将三维顶点位置映射到二维屏幕位置，并对三角形进行着色，好让它们看起来足够真实，同时又以适当的从后到前（\textit{back-to-front}）的顺序呈现。

尽管如何按照有效的从后到前顺序绘制三角形曾是计算机图形学中最重要的研究问题，但现在几乎都是用\textit{z-buffer}来解决，它使用一个特殊的内存缓冲区，以蛮力的方式解决问题。

事实证明，图形管道中使用的几何操作几乎完全可以在四维坐标空间中完成，该空间由三个传统的几何坐标和第四个有助于透视的齐次坐标（\textit{homogeneous coordinate}）组成。这些四维坐标是用 $4 \times 4$ 矩阵和四维向量来操作的。因此，图形管道包含了许多能有效处理、合成这些矩阵和向量的机制。这种四维坐标系是计算机科学中最微妙、最美丽的结构之一，同时也是学习计算机图形学时需要跨越的最大障碍。每本图形学书籍的第一部分都有很大一部分内容是关于这些坐标的。

图像生成的速度很大程度上取决于需要绘制的三角形的数量。由于许多应用中交互性比视觉质量更重要，因此需要尽量减少用于表示模型的三角形数量。此外，如果从远处看模型，需要的三角形数量比从近处看模型时要少。这说明使用不同的细节级别（\textit{LOD, level of detail}）来表示一个模型是很有用的。

\section{数值问题}

许多图形程序实际上只是和三维相关的数值代码。数值问题在这类程序中往往是至关重要的。在 “过去”，要以健壮和可移植的方式处理这些问题是非常困难的，因为机器内部对数值有不同的表示，更糟糕的是，处理异常的方式也不尽相同，互不兼容。幸运的是，几乎所有的现代计算机都遵循IEEE浮点数（\textit{IEEE floating-point}）标准（IEEE标准协会，1985）。该标准允许程序员对“某些数值条件会如何被处理”这种问题做出许多方便的假设。

尽管IEEE浮点数标准有很多在编写数值算法时很有价值的特性，但就图形学中遇到的大多数情况而言只有少数几个特性是至关重要的。首先，也是最重要的，是要了解IEEE浮点标准中实数的三个“特殊”值：
\begin{enumerate}
  \item \textcolor{lightgreen}{无穷大（$\infty$）}：这是一个比其他所有有效数字都要大的有效数字。
  \item \textcolor{lightgreen}{负无穷大（$-\infty$）}：这是一个比其他所有有效数字都要小的有效数字。
  \item \textcolor{lightgreen}{非数字（$\mathrm{NaN}$）}：这是一个由不确定后果的操作产生的无效数字，比如0除以0。
\end{enumerate}

\marginpar{
  \begin{center}
    \begin{note}\\
      IEEE浮点数运算有两种零的表示方法，一种表示法将零视为正数，另一种则将零视为负数。虽然$-0$和$+0$之间的区别一般不重要，但以防万一还是应该牢记于心的。
    \end{note}
  \end{center}
}

IEEE浮点数标准的设计者制定了一些对程序员来说非常方便的规定，而其中不少规则都与上述三个处理异常（比如除以零）的特殊值有关。在这些情况下，异常会被记录下来，但在很多场景中，程序员可以忽略它。具体来说，对于任何正实数$a$，以下涉及除以无穷数的规则都是成立的：
\[
  \begin{aligned}
     & +a /(+\infty)=+0, \\
     & -a /(+\infty)=-0, \\
     & +a /(-\infty)=-0, \\
     & -a /(-\infty)=+0.
  \end{aligned}
\]

其他涉及无穷数的运算的表现与人们所期望的一样。同样对于正实数$a$，其行为如下：
\[
  \begin{aligned}
    \infty+\infty        & =+\infty,      \\
    \infty-\infty        & =\mathrm{NaN}, \\
    \infty \times \infty & =\infty,       \\
    \infty / \infty      & =\mathrm{NaN}, \\
    \infty / a           & =\infty,       \\
    \infty / 0           & =\infty,       \\
    0 / 0                & =\mathrm{NaN}.
  \end{aligned}
\]
布尔表达式中涉及无穷数的规则与预期一致：
\begin{enumerate}
  \item 所有有限的有效数字都小于$+\infty$;
  \item 所有有限的有效数字都大于$-\infty$;
  \item $-\infty$小于$+\infty$.
\end{enumerate}
涉及$\mathrm{NaN}$值的表达式规则比较简单：
\begin{enumerate}
  \item 任何包括$\mathrm{NaN}$的算术表达式的结果都是$\mathrm{NaN}$；
  \item 任何涉及$\mathrm{NaN}$的布尔表达式都是假的。
\end{enumerate}
也许IEEE浮点数标准最有用的地方在于规定了“如何处理除以零的问题”；对于任何正实数$a$，以下涉及除以零值的规则都成立：
\[
  \begin{aligned}
    +a /+0=+\infty, \\
    -a /+0=-\infty.
  \end{aligned}
\]
\marginpar{
  \begin{center}
    \begin{note}\\
      必须留意可能出现负零(-0)的情况！
    \end{note}
  \end{center}
}

如果程序员能对IEEE规则善加利用，那么许多数字计算会变得更加简单。例如，考虑表达式：
\[
  a=\frac{1}{\frac{1}{b}+\frac{1}{c}}
\]
这种表达式会在电阻和透镜相关的问题中出现。如果除以0会导致程序崩溃（在IEEE浮点数标准出现前的许多系统中都是如此），那么就需要两个if语句来检查b或c的小值或零值。相反，在IEEE浮点数标准中，如果$b$或$c$为零，我们会如愿获得$a$的零值。另一种避免特殊检查的常用技术是利用$\mathrm{NaN}$的布尔特性。请看下面的代码段：
\begin{lstlisting}
  a = f(x)
  if(a > 0) then
    do something
\end{lstlisting}
在这里，函数$f$可能会返回“丑陋”的值，如$\infty$或$\mathrm{NaN}$，但$if$条件仍然是明确的：当$a=\mathrm{NaN}$或$a=-\infty$时为假，而$a=+\infty$为真。在决定返回哪些值时要小心，通常$if$语句可以在不检查的情况下做出正确选择。这使得程序更小、更健壮、更高效。

\section{效率}

并没有什么神奇的规则能让代码更加高效。想要高效需要仔细地做权衡，而这些权衡对于不同的架构是不同的。然而在可预见的未来，一个好的启发式方法是，程序员应该更多地关注内存访问模式而不是操作数。这与20年前的最佳启发式方法相反，出现这种转变是因为这20年间内存的速度没有跟上处理器的速度。由于这一发展趋势仍在继续，有限、连贯的内存访问对优化的重要性应该只会增加。

一个合理的优化代码的方法是按以下顺序进行，只采取那些需要的步骤：
\begin{enumerate}
  \item 用最直接的方式编写代码。根据需要即时计算中间结果，而不是将其存储起来；
  \item 在优化模式下进行编译；
  \item 使用现有的任何分析工具来找到关键瓶颈；
  \item 检查数据结构以寻找改善局部性的方法。尽可能让数据单元大小与目标架构上的缓存/页面大小相匹配；
  \item 如果分析工具表明数值计算存在瓶颈，请检查编译器生成的汇编代码是否存在优化空间。重写源代码以解决发现的任何问题。
\end{enumerate}
这些步骤中最重要的是第一个。大多数所谓的“优化”使代码更难读，却没有加快速度。此外，前期花在代码优化上的时间通常更适合用来纠正错误或增加功能。另外要注意旧版《计算机图形学基础》中给出的建议；一些经典的技巧（比如使用整数而不是实数）可能不再加快速度，因为现代CPU在执行浮点数操作时一般都能像执行整数操作一样快。在所有情况下都应该用分析工具来确定任何针对特定机器、编译器的优化是否真的有意义。

\section{图形程序设计和编码}

某些常见的策略在图形编程中往往很有用。在本节中，我们提供了一些建议，当你实现书中学到的方法时，你可能会发现这些建议很有帮助。

\marginpar{
  \begin{center}
    \begin{note}\\
      我坚信KISS（“保持简单、愚蠢”，\textit{"keep it simple, stupid"}）原则，从这个角来看，“将位置、位移放在两个类型中”的论点并不令人信服，不足以证明增加的复杂性。-P.S.
    \end{note}
  \end{center}
}

\marginpar{
  \begin{center}
    \begin{note}\\
      我喜欢把点和向量分开，因为它使代码更易读，并能让编译器捕捉到一些错误。-S.M.
    \end{note}
  \end{center}
}

\subsection{类型设计}

所有图形程序的一个关键部分是为几何实体（如向量和矩阵）以及图形实体（如RGB颜色和图像）提供良好的类型或例程，这些例程应该尽可能的简洁和高效。一个普遍的设计问题是，位置和位移是否应该放在不同的类型中，因为它们有不同的操作。例如，一个位置乘以二分之一没有几何意义，而位移的二分之一却有意义（Goldman, 1985; DeRose, 1989）。在这个问题上人们几乎没有一致的意见，还可能会在图形学从业者中引发数小时的激烈争论，但为了举例说明，我们假设不做这种区分。

这意味着要编写的一些基本类型包括：
\begin{itemize}
  \item \textcolor{lightgreen}{二维向量（\textit{vector2}）}。一个用于存储$x$和$y$分量的二维向量类型，它将这些分量存储在一个长度为2的数组中，这样就可以很好地支持索引操作。你还应该包括向量加法、向量减法、点积、叉积、标量乘法和标量除法的操作。
  \item \textcolor{lightgreen}{三维向量（\textit{vector3}）}。一个类似于二维向量的三维向量类型。
  \item \textcolor{lightgreen}{h向量（\textit{hvector}）}。一个有四个分量的齐次向量（见第8章）。
  \item \textcolor{lightgreen}{\textit{RGB}}。RGB颜色类型存储三个分量，此外还应该包括RGB加法、RGB减法、RGB乘法、标量乘法和标量除法之类的操作。
  \item \textcolor{lightgreen}{变换（\textit{transform}）}。一个用于变换的 $4 \times 4$ 矩阵，还应该包括一个矩阵乘法和成员函数来应用于位置、方向和表面法向量。如第七章所示，这些都是不同的。
  \item \textcolor{lightgreen}{图像（\textit{image}）}。一个具有输出操作的、由RGB像素组成的二维数组。
\end{itemize}
此外，由你决定要不要为时间间隔、正交基和坐标系添加类型。

\marginpar{
  \begin{center}
    \begin{note}\\
      你也可以为单位向量建立一个特殊的类型，尽管我个人觉得不是很有必要。-P.S.
    \end{note}
  \end{center}
}

\subsection{单精度浮点数与双精度浮点数的比较 }

现代架构表明，减少内存的使用和保持内存访问的连贯性是实现高效的关键，所以最好使用单精度数据。然而为了避免数字问题又需要双精度数据进行运算。这方面的权衡取决于你的程序，但最好能在类型的定义中设定一个默认值。

\marginpar{
  \begin{center}
    \begin{note}\\
      我建议在几何计算中使用双精度浮点数，在颜色计算中使用单精度。对于占据大量内存的数据，如三角形网格，我建议存储为单精度数据，但当通过成员函数访问数据时，要转换为双精度。—P.S.
    \end{note}
  \end{center}
}

\marginpar{
  \begin{center}
    \begin{note}\\
      我主张所有的计算都使用单精度浮点数，直到发现在代码的特定部分必须使用双精度浮点数。—S.M.
    \end{note}
  \end{center}
}

\subsection{调试图形程序}

如果你四处打听可能会发现，随着程序员经验的增加，他们越来越少地使用传统的调试器。其中一个原因是，对于复杂的程序来说，使用这样的调试器相比简单的程序在使用时更加困难；另一个原因是，最严重的错误是概念上的错误（也就是说实现了错误的东西），这就很容易把大量的时间浪费在检查变量值上，而不能发现真正的错误。我们发现有几种调试策略对图形学开发特别有用。

\subsubsection{科学的方法}

在图形程序中，有一种替代传统调试的方法往往很有用。它的缺点在于它与计算机程序员在职业生涯早期被教导不要做的事情非常相似，所以这样做时你可能会觉得“很调皮”：我们先创建一个图像，观察它有什么问题。然后我们对导致问题的原因提出一个假设，并对其进行测试。例如在一个光线追踪程序中，可能会有许多看起来有些随机的暗色像素。这是典型的“阴影失真（\textit{shadow acne}）”问题，大多数人在写光线追踪程序时都会遇到。传统的调试在这里是没有用的，相反，我们必须意识到阴影射线是打在被着色的表面上的。我们可能会注意到，黑点的颜色是环境色，所以直接照明是缺失的。直接照明可以在阴影中被关闭，所以你可以假设这些本该在亮处的点被错误地标记为在阴影中。为了验证这个假设，我们可以关闭阴影检查并重新编译。这将表明这些是错误的阴影测试，我们可以继续我们的调查工作。这种方法在实践中有时很好用的关键原因是，我们从不需要发现一个错误的值、或真正明确我们的概念性错误。相反，我们只是通过实验缩小了概念性错误的范围。通常情况下，只需要几次试验就可以追踪到事情的真相，这种类型的调试是很愉快的。

\subsubsection{图像作为编码调试的输出}

在许多情况下，从图形程序中获得调试信息的最简单方式是输出图像本身。如果你想知道在每个像素上都会运行的计算中的某个变量值，那你可以临时修改你的程序，把这个值直接复制到输出图像上，并跳过通常要进行的其他计算。例如，如果你怀疑表面法线导致了着色的问题，你可以直接将法向量复制到图像上（$x$转为红色，$y$转为绿色，$z$转为蓝色），结果就是在计算中实际使用的向量的颜色编码图。或者，如果你怀疑某个特定的值有时超出了它的有效范围，就可以让你的程序在发生这种情况的地方使用鲜红色的像素。其他常见的技巧包括用明显的颜色画出表面的背面（当它们应该是不可见的情况下）、用物体的ID给图像着色、或者用像素的计算量来着色。

\subsubsection{使用调试器}

在某些场景中（特别是当正确步骤似乎导致结果不一致时），当我们想要观察程序中究竟发生了什么时，调试器仍然是无法取代的。麻烦在于图形程序往往涉及多次执行相同的代码（例如，每个像素执行一次或每个三角形执行一次），这导致从一开始就在调试器中逐步执行代码是完全不现实的。而且最困难的错误通常只发生在复杂的输入上。

一个有用的方法是为该错误“设置一个陷阱”。首先，确保你的程序是确定的——在单线程中运行并确保所有的随机数都是由固定的种子计算出来的。然后找出有错误的像素或三角形，并在你怀疑不正确的代码前添加一个只会在可疑情况下执行的语句。例如，如果你发现像素（126，247）出现了错误，那么就添加
\begin{lstlisting}
  if(x = 126 and y = 247) then
    print "blarg!"
\end{lstlisting}
\marginpar{
  \begin{center}
    \begin{note}\\
      使用固定的随机数种子的特殊调试模式很有用。
    \end{note}
  \end{center}
}
如果你在打印语句上设置一个断点，你就可以在你感兴趣的像素被计算出来之前进入调试器。有些调试器有一个“条件断点”功能，可以在不修改代码的情况下达到同样的效果。

在程序崩溃的情况下，传统的调试器对于确定崩溃的地点很有用。然后你应该在程序中开始回溯，使用断言和重新编译从而找出程序出错的地方。这些断言应该被留在程序中，以备将来可能出现的错误。这也就意味着要避免传统的步进过程，因为这样就不会在程序中添加有价值的断言。

\subsubsection{调试过程的数据可视化}

通常情况下，我们很难理解你的程序在做什么，因为它在最终出错之前计算了大量的中间结果。这种情况类似于测量大量数据的科学实验，有一个共通的解决办法：为自己制作合理的图表和插图以了解数据的含义。例如在光线追踪器中，你可能会编写将光线树可视化的代码，这样你就可以看到哪些路径对一个像素的贡献，或者在图像重采样程序中，你可能会做一些图来显示输入中的所有采样点。编写代码以可视化程序内部状态所花费的时间，也可以在优化程序时通过更好地了解程序的行为来得到回报。

\marginpar{
  \begin{center}
    \begin{note}\\
      我喜欢把调试中打印出来的语句格式化，这样输出的结果恰好是一个MATLAB\textsuperscript{\textregistered}或Gnuplot脚本，可以做出有帮助的图。-S.M.
    \end{note}
  \end{center}
}

\section*{说明}
关于软件工程的讨论受到《Effective C++》系列（Meyers, 1995, 1997）、《Extreme Programming Explained: Embrace Change》（Beck \& Andres, 2004）和《The Practice of Programming》（Kernighan \& Pike, 1999）的影响。关于实验性调试的讨论基于和Steve Parker的讨论。

有许多与计算机图形学有关的年度会议，包括ACM SIGGRAPH和SIGGRAPH Asia、Graphics Interface、Game Developers Conference（GDC）、Eurographics、Pacific Graphics、High Performance Graphics、Eurographics Symposium on Rendering以及IEEE VisWeek。通过网络搜索，可以很容易找到这些会议的名称。
